#! /usr/bin/env python3
# coding = uft-8

class Solution(object):
    def threeSum(self, nums, target):
        result = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if j != i + 1 and nums[j] == nums[j - 1]:
                    j += 1
                    continue
                if k != len(nums) - 1 and nums[k] == nums[k + 1]:
                    k -= 1
                    continue
                sum = nums[i] + nums[j] + nums[k]
                if sum > target:
                    k -= 1
                elif sum < target:
                    j += 1
                else:
                    result.append([nums[i], nums[j], nums[k]])
                    k -= 1
                    j += 1
        return result


    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            _target = target - nums[i]
            _res = self.threeSum(nums[i + 1:], _target)
            print(_res)
            for j in _res:
                j.append(nums[i])
            result.extend(_res)
        return result

s = Solution()
print(s.fourSum([-1,-5,-5,-3,2,5,0,4], -7))